package com.myworld.datastructure.tree;

public class MaxHead{
    /**堆中的元素:
     * weight: 权重
     * */
    private HeadElement[] data;
    /**当前堆中元素个数*/
    private int size;
    /**堆得最大容量*/
    private int apacity;

    public MaxHead(int maxSize,HeadElement[] headElements){
       buildHeap(maxSize,headElements);
    }

    public MaxHead(int maxSize){
        create(maxSize);
    }

    public boolean isNull(){
        return  size==0;
    }

    /**
     * 创建一个空的最大堆
     * @param maxSize
     * @return
     */
    public MaxHead create(int maxSize){
        apacity=maxSize;
        data=new HeadElement[maxSize+1];
        /*定义哨兵，为大于堆中所有的元素,便于以后的操作*/
        data[0]=new HeadElement(Integer.MAX_VALUE,null);
        size=0;
        return this;
    }

    /**
     * 将元素插入到最大堆
     * @param item
     * @return
     */
    public boolean insert(HeadElement item){
        /*判断最大堆是否已满*/
        if(size==apacity){
            return false;
        }
        int i=++size;
       for (;data[i/2].getWeight()<item.getWeight();i/=2){
            data[i]=data[i/2];
       }
       data[i]=item;
        return true;
    }

    /**
     * 最大堆中的删除操作
     */
    public HeadElement deleteMax(){
        /**判断最大堆是否为空*/
        if(size==0){
            throw new RuntimeException("最大堆已为null,不能删除");
        }
        HeadElement maxEelement=data[1];
        data[1]=data[size--];
        percDown(1);
        return maxEelement;
    }

    /**
     * 下沉操作
     * @param index
     */
    private void percDown(int index){
        /*取出根节点存放的值*/
        HeadElement item=data[index];
        int parent, child;
        for(parent=index;parent*2<=size;parent=child){
            child=parent*2;
            if(child!=size&& data[child+1].getWeight()>data[child].getWeight()){
                child++; //child指向左右子树中较大的节点
            }
            if(item.getWeight()>=data[child].getWeight()) break;
            data[parent]=data[child];
        }
        data[parent]=item;
    }

    public MaxHead buildHeap(int maxSize,HeadElement[] headElements){
        data=new HeadElement[maxSize+1];
        data[0]=new HeadElement(Integer.MAX_VALUE,null);
        size=headElements.length;
        apacity=maxSize;
        for (int i=0;i<headElements.length;i++){
            data[i+1]=headElements[i];
        }
        for(int i=size/2;i>0;i--){
            percDown(i);
        }
        return  this;
    }

}
